package com.coder.exercise;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class PostorderTraversal {
	
	public class StackNode{
		TreeNode node; 
		boolean isFirst;		//0:left,1:right
		StackNode(TreeNode node,boolean isSecond){
			this.node = node;
			this.isFirst = isSecond;
		}
	}
	
	ArrayList<Integer> list = new ArrayList<Integer>();
	Stack<StackNode> stack = new Stack<StackNode>();
	
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null){
        	return list;
        }
        
        StackNode sNode = null;
     
        do{
	        while(root!=null){
	        	stack.push(new StackNode(root,true));
	        	root = root.left;
	        }
	        
	        boolean continuePop = true;
	        
	        while(continuePop && !stack.isEmpty()){
	        	sNode = stack.pop();
	        	if(sNode.isFirst){
	        		continuePop = false;
	        		sNode.isFirst = false;
	        		stack.push(sNode);
	        		root = sNode.node.right;
	        	}else{
	        		list.add(sNode.node.val);
	        	}
	        }
        }while(!stack.isEmpty());
        
    	return list;
    }
    
//    public static void main(String[] args) {
//		TreeNode root = TreeNode.getInstance();
//		PostorderTraversal sot = new PostorderTraversal();
//		System.out.println(sot.postorderTraversal(root));
//	}
}